/**
 * //以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返
 * //回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * //输出：[[1,6],[8,10],[15,18]]
 * //解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：intervals = [[1,4],[4,5]]
 * //输出：[[1,5]]
 * //解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= intervals.length <= 10⁴
 * // intervals[i].length == 2
 * // 0 <= starti <= endi <= 10⁴
 * //
 * // Related Topics 数组 排序 👍 1459 👎 0
 */

package com.xixi.basicAlgroithms.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class ID00056MergeIntervals {
    public static void main(String[] args) {

        Solution solution = new ID00056MergeIntervals().new Solution();
        int[][] result = solution.merge(new int[][]{{1,3},{2,6},{8,10},{15,18}});
        for(int i = 0; i <result.length; ++i ){
            System.out.println(result[i][0] + "," + result[i][1]);

        }
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] merge(int[][] intervals) {

            if(intervals.length == 0){
                return  new int[1][2];
            }

            Arrays.sort(intervals, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] - o2[0];
                }
            });



            List<int[]> result = new ArrayList<>();
            //找到两个相邻的数字，如果差大于1，就新建一个区间

            for(int i = 0; i < intervals.length; ++i){
                int intervalStart = intervals[i][0];
                int intervalEnd = intervals[i][1];

                if(result.size() == 0 || result.get(result.size() - 1)[1] < intervalStart){ //新增区间的情况
                    result.add(new int[]{intervalStart, intervalEnd});
                }else { //合并结果区间尾部大于当前遍历的区间头部，便将当前区间合并进来
                    result.get(result.size() -1)[1] = Math.max(result.get(result.size() -1)[1], intervalEnd);
                }



            }

            return result.toArray(new int[result.size()][]);
        }




        public void quickSort(int[] allBoundaries, int start, int pivot){

            if(start > pivot){
                return;
            }

            int newPivot = partition(allBoundaries, start, pivot);

            quickSort(allBoundaries, start, newPivot -1);
            quickSort(allBoundaries, newPivot + 1, pivot);

        }

        public int partition(int[] allBoundaries, int start, int pivot){

            int pivotValue = allBoundaries[pivot];
            int nextPivot = start;
            for(int i = start; i < pivot; ++i){
                if(allBoundaries[i] < pivotValue){
                    swap(allBoundaries, nextPivot,i);
                    ++nextPivot;
                }
            }
            swap(allBoundaries, nextPivot, pivot);

            return nextPivot;

        }

        public void swap(int[] arr, int a, int b){
            int tmp = arr[a];
            arr[a] = arr[b];
            arr[b] = tmp;

        }

        public int[][] recursive(int[][] intervals, int head, int end) {
            if (head == end) {
                int[][] oneInterval = new int[1][];
                oneInterval[0] = intervals[head];
                return oneInterval;
            }

            //计算新的分区
            int pivot = (end + head) / 2;
            //两边分别归并排序
            int[][] former = recursive(intervals, head, pivot);
            int[][] tail = recursive(intervals, pivot + 1, end);


            if (former == null) return tail;
            if (tail == null) return former;

            //合并头尾数组
            int[] formerEnd = former[former.length - 1];
            int[] tailHead = tail[0];
            if (formerEnd[1] >= tailHead[0]) {
                int[] middleInterval = new int[]{Math.min(formerEnd[0], tailHead[0]), Math.max(formerEnd[1], tailHead[1])}; //合并头尾数组的中间部分
                int[][] result = new int[former.length + tail.length - 1][];
                int i = 0;
                while (i < (former.length - 1)) {
                    result[i] = former[i];
                    ++i;
                }
                result[i] = middleInterval; //中间数组，前去尾，后掐头


                for(int j = 1; j < tail.length ; ++j){
                    result[i] = tail[j];
                    i++;
                }

                return result;
            }else{
                int[][] result = new int[former.length + tail.length][];
                int i = 0;
                while (i < former.length) {
                    result[i] = former[i];
                    ++i;
                }

                for(int j = 0; j < tail.length ; ++j){
                    result[i] = tail[j];
                    i++;
                }

                return result;
            }



    }


}
//leetcode submit region end(Prohibit modification and deletion)




}